//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 105 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 双指针 字符串 Sliding Window 
// 👍 921 👎 0
#include <iostream>
#include <vector>

using namespace std;


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    string minWindow(string s, string t) {

        int left = 0,right = 0,need = t.size(),minStart = 0,minLen = INT_MAX;
        int m[128] = {0};
        string res = "";

        for (char c : t){
            ++m[c];
        }
        while (right < s.size()){
            if (m[s[right]] > 0)
                --need;
            --m[s[right]];
            ++right;
            while (need == 0){
                if (right - left < minLen){
                    minStart = left;
                    minLen = right - left;
                }
                ++m[s[left]];
                if (m[s[left]] > 0){
                    ++need;
                }
                ++left;
            }
        }
        if (minLen != INT_MAX)
            res = s.substr(minStart,minLen);
        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
